package leetcode.code0187;

import java.util.ArrayList;
import java.util.List;

public class Solution2 extends Solution187 {

	@Override
	public List<String> findRepeatedDnaSequences(String s) {
		int len = s.length();
		List<String> ans = new ArrayList<>();
		if (len < 11) {
			return ans;// 不足11位一点机会没有
		}
		char[] cs = s.toCharArray();
		int cur = 0;
		for (int i = 0; i < 10; i++) {// 长度10的窗口,第一个出现的字符串,转换成数字cur
			cur = (cur << 2) | map(cs[i]);
		}
		int cut = 0b11111111111111111111;// 超长部分剪掉,只留下末尾20位
		Boolean[] table = new Boolean[cut + 1];// null未出现,第一次出现标记为false,第二次标记为true,最大也就全是1,作为下标数组长度+1
		table[cur] = false;// 第一次出现
		for (int i = 10; i < len; i++) {
			cur = ((cur << 2) | map(cs[i])) & cut;// 挪动窗口, | 挪入, & 挪出
			Boolean has = table[cur];
			if (has == null) {// 未出现过
				table[cur] = false;// 第一次出现
			} else if (!has) {// 第二次出现次出现
				ans.add(new String(cs, i - 9, 10));
				table[cur] = true;// 标记为true 再见着就不收录到ans了
			}
		}
		return ans;
	}

	private int map(char c) {
		if (c == 'A') {
			return 0b00;
		}
		if (c == 'C') {
			return 0b01;
		}
		if (c == 'G') {
			return 0b10;
		}
		if (c == 'T') {
			return 0b11;
		}
		return -1;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();

	}

}
